package rbtree;

public class RBTree {

    static class RBTreeNode{
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode parent;
        public int val;
        public COLOR color;

        public RBTreeNode(int val) {
            this.val = val;
            this.color = COLOR.RED;//新建的节点默认是红色的
        }
    }
    public RBTreeNode root;
    public boolean insert(int val){
        RBTreeNode node=new RBTreeNode(val);
        if(root==null){
            root=node;
            root.color=COLOR.BLACK;
            return true;
        }
        RBTreeNode parent=null;
        RBTreeNode cur=root;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){
                return false;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
        if(parent.val<val){
            parent.right=node;
        }else{
            parent.left=node;
        }
        node.parent=parent;
        cur=node;
        while(parent!=null && parent.color==COLOR.RED){
            RBTreeNode grandFather=parent.parent;
            if(parent==grandFather.left){
                RBTreeNode uncle=grandFather.right;
                if(uncle!=null &&uncle.color==COLOR.RED){
                    parent.color=COLOR.BLACK;
                    uncle.color=COLOR.BLACK;
                    grandFather.color=COLOR.RED;
                    cur=grandFather;
                    parent=cur.parent;
                }else{
                    //uncle不存在 或者uncle是黑色的
                    if(cur==parent.right){
                        rotateLeft(parent);
                        RBTreeNode tmp=parent;
                        parent=cur;
                        cur=tmp;
                    }
                    rotateRight(grandFather);
                    grandFather.color=COLOR.RED;
                    parent.color=COLOR.BLACK;
                }
            }else{
                //parent是grandfather的右节点
                RBTreeNode uncle=grandFather.left;
                if(uncle!=null &&uncle.color==COLOR.RED){
                    parent.color=COLOR.BLACK;
                    uncle.color=COLOR.BLACK;
                    grandFather.color=COLOR.RED;
                    cur=grandFather;
                    parent=cur.parent;
                }else{
                    //uncle不存在 或者uncle是黑色的
                    if(cur==parent.left){
                        rotateRight(parent);
                        RBTreeNode tmp=parent;
                        parent=cur;
                        cur=tmp;
                    }
                    rotateLeft(grandFather);
                    grandFather.color=COLOR.RED;
                    parent.color=COLOR.BLACK;
                }
            }
        }
        root.color=COLOR.BLACK;
        return true;
    }
    //右旋
    private void rotateRight(RBTreeNode parent) {
        //先定义subL、subR的位置
        RBTreeNode subL=parent.left;
        RBTreeNode subLR=subL.right;
        //旋转
        parent.left=subLR;
        subL.right=parent;
        if(subLR!=null){
            subLR.parent=parent;
        }
        RBTreeNode pParent=parent.parent;
        parent.parent=subL;

        //检查当前节点是不是根节点
        if(parent==root){
            root=subL;
            root.parent=null;
        }else{
            //不是根节点 判断是左子树还是右子树
            if(pParent.left==parent){
                pParent.left=subL;
            }else{
                pParent.right=subL;
            }
            subL.parent=pParent;
        }
    }
    //左旋
    private void rotateLeft(RBTreeNode parent) {
        //先定义subL、subR的位置
        RBTreeNode subR=parent.right;
        RBTreeNode subRL=subR.left;
        //旋转
        parent.right=subRL;
        subR.left=parent;
        if(subRL!=null){
            subRL.parent=parent;
        }
        RBTreeNode pParent=parent.parent;
        parent.parent=subR;

        //检查当前节点是不是根节点
        if(parent==root){
            root=subR;
            root.parent=null;
        }else{
            //不是根节点 判断是左子树还是右子树
            if(parent==pParent.left){
                pParent.left=subR;
            }else{
                pParent.right=subR;
            }
            subR.parent=pParent;
        }
    }
    //判断是否为红黑树
    public boolean isRBTree() {
        if (root == null) {
            return true;
        }
        if(root.color!=COLOR.BLACK){
            System.out.println("违反了根节点是黑色的规则");
        }
        //存储当前红黑树中最左侧路径的黑色节点数
        int blackNum=0;
        RBTreeNode cur=root;
        while(cur!=null){
            if(cur.color==COLOR.BLACK){
                blackNum++;
            }
            cur=cur.left;
        }
        //检查是否出现两个相连的节点都是红色的情况 并且 每条路径上黑色节点数是否相同
        return checkRedColor(root) && checkBlackNum(root,0,blackNum);
    }
    private boolean checkBlackNum(RBTreeNode root,int pathBlackNum,int blackNum){
        if(root==null){
            return true;
        }
        if(root.color==COLOR.BLACK){
            pathBlackNum++;
        }
        if(root.left==null && root.right==null){
            if(pathBlackNum!=blackNum){
                System.out.println("违反了每一条路径上黑色节点数相等的规则");
                return false;
            }
        }
        return checkBlackNum(root.left,pathBlackNum,blackNum) && checkBlackNum(root.right,pathBlackNum,blackNum);
    }
    private boolean checkRedColor(RBTreeNode root){
        if(root==null){
            return true;
        }
        if(root.color==COLOR.RED){
            RBTreeNode parent=root.parent;
            if(parent.color==COLOR.RED){
                System.out.println("违反了出现两个红色节点相连的规则");
                return false;
            }
        }
        return checkRedColor(root.left) && checkRedColor(root.right);
    }
    public void inorder(RBTreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

}
